package linkedList;

/**
 * 92. 反转链表 II
 *
 * 给你单链表的头指针 head 和两个整数left 和 right ，其中left <= right 。
 * 请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 *
 */
public class ReverseLinkedList_92 {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) {
            return head;
        }

        // dummy指针，head一直在遍历，使用dummy指针返回结果
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        // pre节点为开始反转的前一个节点
        ListNode pre = dummy;
        for (int i = 1; i < left; i++) {
            pre = pre.next;
        }

        // head为开始反转的第一个节点
        head = pre.next;
        // mov节点从开始反转的节点开始记录，直到最后一个反转的节点
        // 由于1 <= left <= right <= n，nxt不会为null
        for (int i = left; i < right; i++) {
            ListNode nxt = head.next;
            head.next = nxt.next;
            nxt.next = pre.next;
            pre.next = nxt;
        }
        return dummy.next;
    }
}
